#define _CRT_SECURE_NO_WARNINGS
//class Solution {
//public:
//    void hanota(vector<int>& A, vector<int>& B, vector<int>& C) {
//        dfs(A, B, C, A.size());
//    }
//    void dfs(vector<int>& A, vector<int>& B, vector<int>& C, size_t n)
//    {
//        if (n == 1)
//        {
//            C.push_back(A.back());
//            A.pop_back();
//            return;
//        }
//
//        dfs(A, C, B, n - 1);
//        C.push_back(A.back());
//        A.pop_back();
//        dfs(B, A, C, n - 1);
//    }
//};
//
//
//class Solution {
//public:
//    ListNode* reverseList(ListNode* head) {
//        if (head == nullptr)
//            return nullptr;
//        if (head->next == nullptr)
//        {
//            return head;
//        }
//
//        ListNode* ret = reverseList(head->next);
//        head->next->next = head;
//        head->next = nullptr;
//        return ret;
//    }
//};
//
//class Solution {
//public:
//    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
//        if (list1 == nullptr)
//            return  list2;
//        if (list2 == nullptr)
//            return list1;
//        if (list1->val < list2->val)
//        {
//            list1->next = mergeTwoLists(list1->next, list2);
//            return list1;
//        }
//        else
//        {
//            list2->next = mergeTwoLists(list1, list2->next);
//            return list2;
//        }
//
//    }
//};
//
//
//class Solution {
//public:
//    ListNode* swapPairs(ListNode* head) {
//        if (head == nullptr || head->next == nullptr)
//        {
//            return head;
//        }
//        ListNode* newhead = swapPairs(head->next->next);
//        ListNode* ret = head->next;
//        head->next->next = head;
//        head->next = newhead;
//        return ret;
//    }
//};
#include <iostream>
using namespace std;

struct TreeNode
{
    TreeNode(int x)
    {
        val = x;
        left = nullptr;
        right = nullptr;
    }
    int val;
    TreeNode* left;
    TreeNode* right;
};


//int sumNumbers(TreeNode* root) {
//    if (root == nullptr)
//        return 0;
//    return sum(root, 0);
//}
//int sum(TreeNode* root, int val)
//{
//    if (root == nullptr)
//        return val;
//    int tmp = val * 10 + root->val;
//    if (root->left == nullptr && root->right == nullptr)
//        return tmp;
//    if (root->left == nullptr)
//        return sum(root->right, tmp);
//    if (root->right == nullptr)
//        return sum(root->left, tmp);
//
//    return sum(root->left, tmp) + sum(root->right, tmp);
//}

class Solution {
public:
    long long prev = (long long)INT_MIN - 1;
    bool isValidBST(TreeNode* root) {
        if (root == nullptr)
            return true;
        if (root->right == nullptr && root->left == nullptr)
        {
            if (root->val > prev)
            {
                prev = root->val;
                return true;
            }
            return false;
        }
        bool left = isValidBST(root->left);
        if (root->val > prev)
        {
            prev = root->val;
        }
        else
        {
            return false;
        }
        bool right = isValidBST(root->right);
        return left && right;
    }

};
int main()
{
    TreeNode n1(2);
    TreeNode n2(1);
    TreeNode n3(3);
    n1.left = &n2;
    n1.right = &n3;
    //sumNumbers(&n1);
    isValidBST(&n1);
    return 0;
}

//double myPow(double x, int n) {
//    if (n == 0)
//        return 1;
//    if (n == 1)
//        return x;
//    if (n == -1)
//        return 1 / x;
//    if (n % 2 == 0)
//    {
//        double ret = myPow(x, n / 2);
//        return ret * ret;
//    }
//    else
//    {
//        double ret = myPow(x, n / 2);
//        if (n < 0)
//            return ret * ret * (1 / x);
//        return ret * ret * x;
//    }
//}
//int main()
//{
//    double ret = myPow(2, -2);
//    cout << ret << endl;
//	return 0;
//}
//
//
//class Solution {
//public:
//    bool evaluateTree(TreeNode* root) {
//        if (root->left == nullptr && root->right == nullptr)
//        {
//            return root->val == 1;
//        }
//        else
//        {
//            if (root->val == 2)
//                return evaluateTree(root->left) || evaluateTree(root->right);
//            else
//                return evaluateTree(root->left) && evaluateTree(root->right);
//        }
//
//    }
//};